// Package tree
/*

方法1：递归（深度优先搜索）
时间复杂度：O(min(m,n)) 当两颗树中其中一棵树先遍历完后就不会再继续合并了，所以时间复杂度为较少的那颗数的节点数
空间复杂度：O(min(m,n)) 取决于递归调用栈

case1:

r:

递归的技巧，对下一层进行递归操作时，将递归函数当作已经功能的函数来使用
在处理多情况时代码不够优雅，如果一个为nil可以直接返回另一个时，直接return，排除情况
if root1 == nil {
	return root2
}
if root2 == nil {
	return root1
}
*/
package tree

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	if root1 == nil {
		return root2
	}
	if root2 == nil {
		return root1
	}
	root1.Val += root2.Val
	root1.Left = mergeTrees(root1.Left, root2.Left)
	root1.Right = mergeTrees(root1.Right, root2.Right)
	return root1
}
